Album được phát hành tại Vương quốc Anh vào tháng 9 năm 1970, nơi doanh số bán đĩa được tăng lên nhờ thành công của đĩa đơn "Paranoid". "Đĩa đơn ấy thu hút những đứa trẻ vui nhộn", Iommi kể lại trong những câu ghi chú cho Reunion vào năm 1998. "Chúng tôi thấy mọi người nhảy múa khi chúng tôi thể hiện nó và chúng tôi quyết định rằng mình không ra đĩa đơn trong một thời gian dài để giữ lòng trung thành với người hâm mộ yêu thích chúng tôi trước khi chúng tôi trở nên nổi tiếng." Việc phát hành Paranoid tại Mỹ bị hoãn cho đến tháng 1 năm 1971,[25] vì album Black Sabbath vẫn nằm trong bảng xếp hạng vào thời điểm phát hành tại Anh. Paranoid đạt hạng 12 tại Hoa Kỳ vào tháng 3 năm 1971,[26] hầu như không được phát sóng trên đài phát thanh.[10] Từ các bài đánh giá đương thời, một cây viết chưa được ghi nhận trên Disc khen ngợi album, tuyên bố âm nhạc của nhóm là "chặt chẽ, ồn ào, đơn giản và thú vị" với chất liệu dựa trên "những đoạn riff đơn giản, hấp dẫn [...] với ca từ không đưa chúng vào thế hệ của Dylan."[27]

Trong một bài đánh giá tái nhìn nhận, Steve Huey của AllMusic nhắc đến Paranoid là "một trong những album heavy metal vĩ đại nhất và giàu ảnh hưởng nhất mọi thời đại"; album "đã định nghĩa âm thanh và phong cách của heavy metal hơn bất kỳ đĩa nhạc nào khác trong lịch sử nhạc rock".[15] Ben Mitchell từ Blender thì cho rằng đây là "album nhạc metal hay nhất mọi thời đại".[16] Theo Joe Levy của Rolling Stone, "Sabbath cai trị những đứa trẻ u sầu ở thập niên 70" và "gần như mọi ban nhạc heavy-metal và extreme rock trong ba thập kỷ qua", kể cả Metallica, Nirvana và Slipknot, đều "có một món nợ tôn sùng" những đoạn riff guitar "nghiền nát" của Iommi, "phần nhịp Visigoth" của Ward và Butler cùng "tiếng kêu khắc khoải" của Osbourne trên các bản nhạc như "Paranoid", "Iron Man" và "War Pigs".[28] Robert Christgau tỏ ra kém nhiệt tình hơn trong Christgau's Record Guide: Rock Albums of the Seventies (1981), ông thấy rằng mình chẳng thể coi trọng âm nhạc đề tài kinh dị của ban nhạc đủ để đánh giá đúng như bất cứ thứ gì khác ngoài "camp", lưu ý rằng title cut đặc biệt "đáng sợ". Tuy nhiên, ông lưu ý rằng ban nhạc coi độ nặng của âm nhạc là "khắc nghiệt đến không ngờ".[17]

Album hiện đang đứng ở vị trí số 139 trong danh sách 500 album hay nhất mọi thời đại của tạp chí Rolling Stone. Thành công trên bảng xếp hạng của Paranoid cho phép ban nhạc lưu diễn ở Mỹ lần đầu tiên vào tháng 10 năm 1970, dẫn đến phát hành đĩa đơn thứ hai của album là "Iron Man". Mặc dù không lọt nổi top 40, "Iron Man" vẫn là một trong những bài hát nổi tiếng nhất của Black Sabbath, đồng thời là đĩa đơn xếp hạng cao nhất tại Hoa Kỳ của ban nhạc.[29] Tính đến năm 2014, Paranoid là album bán chạy nhất của Black Sabbath, đã bán ra 1,6 triệu bản tại Hoa Kỳ kể từ khi bắt đầu kỷ nguyên SoundScan.[30]